\documentclass[10pt]{article}
\usepackage{amsmath}
\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

\newcommand{\problem}[2][No]{\noindent{\sc Problem #1.} #2}
\newcommand{\solution}{\noindent{\sc Solution.}}
\newcommand{\answer}[1]{\noindent{\sc Answer. }#1}
\newcommand{\complexity}{\noindent{\sc Complexity }}
\newcommand{\reference}{\noindent{\sc Reference }}
\newcommand{\seealso}{\noindent{\sc See Also }}

\newcommand{\given}{\,|\,}
\newcommand{\divides}{\,|\,}
\newcommand{\BigO}{\mathcal{O}}

\newcommand{\vl}{\mathbf{l}}

\begin{document}

\problem[181]{Investigating in how many ways objects of two different colors can be grouped.}

Three black objects B and one white object W can be grouped in 7 ways, as follows:

(BBBW) (B,BBW) (B,B,BW) (B,B,B,W) (B,BB,W) (BBB,W) (BB,BW) 

In how many ways can sixty black objects B and forty white objects W be thus grouped?

\solution

% Let's start from the simpler case of grouping only one color of objects. Let $f(n)$ be the number of ways to group $n$ identical objects. We count the grouping by fixing the largest groups first, and then count the smaller ones. 

% Formally, let $f(n;k)$ be the number of ways to group $n$ identical objects with the largest group containing no more than $k$ elements. Then we can find the following recurrence relation
% \[
% f(n;k) = \sum_{i=0}^{\lfloor n/k \rfloor} f(n-ik; k-1)
% \]
% with boundary condition $f(n;1)=1$. Note that $f(n)=f(n;n)$.

Let's start from the simpler case of grouping only one color of objects. Let $p(n)$ be the number of ways to group $n$ identical objects.\footnote{In fact, $p(n)$ is called the \emph{partition function}. See the Reference section for details.} 
We can count the grouping by fixing the largest groups first, and then count the smaller ones. 

Formally, let $p(n;k)$ be the number of ways to group $n$ identical objects with the largest group containing at most $k$ elements. It is easy to see that $p(0;0)=1$, $p(n;0)=0$ for $n \ge 1$, and $p(n;k)=p(n;n)$ for $k>n$. For $1 \le k \le n$, we find the following recurrence relation
\[
p(n; k) = p(n-k; k) + p(n; k-1) .
\]
Note that what we need is simply $p(n)=p(n;n)$.

Now we extend the above method to solve the grouping of two colors of objects. We divide the groups into two types: \emph{mixing groups} and non-mixing groups. Mixing groups contain objects from both colors, and non-mixing groups contain objects of the same color. 

We count the number of ways to organize mixing groups first. Let $g(m_1,m_2)$ be the number of ways to group $m_1$ black objects and $m_2$ white objects into mixing groups. It follows easily that that the total number of grouping given $m_1$ and $m_2$ is $f(n_1-m_1) \times f(n_2-m_2) \times g(m_1, m_2)$. Therefore, if we know $g(m_1,m_2)$, we can easily find the answer to this problem as
\[
h(n_1,n_2) = \sum_{m_1=0}^{n_1} \sum_{m_2=0}^{n_2} f(n_1-m_1) f(n_2-m_2) g(m_1,m_2) .
\]

We use a similar approach as above to find $g(m_1,m_2)$. Let $g(m_1,m_2;k_1,k_2)$ be the number of ways to group $m_1$ black objects and $m_2$ white objects into mixing groups, where every group contains at most $k_1$ black objects and $k_2$ white objects. Then we can find the following recurrence relation
\begin{align}
p(n_1,n_2; k_1,k_2) 
&= p(n_1-k_1,n_2-k_2;k_1,k_2) \notag \\
&+ p(n_1,n_2;k_1-1,k_2) \notag \\
&+p(n_1,n_2; k_1,k_2-1) \notag \\
&- p(n_1,n_2;k_1-1,k_2-1) \notag
\end{align}
with boundary conditions
\begin{align}
g(0,0; k_1,k_2) &= 1 , \notag
\end{align}
and for $n_1 + n_2 > 0$,
\begin{align}
g(n_1,n_2; k_1,0) &= 0 , \notag \\
g(n_1,n_2; 0,k_2) &= 0 . \notag 
\end{align}

\answer{None}

\complexity

Time complexity: $\BigO(n_1^2 n_2^2)$

Space complexity: $\BigO(n_1^2 n_2^2)$

\reference

http://mathworld.wolfram.com/PartitionFunctionP.html

http://en.wikipedia.org/wiki/Partition\_(number\_theory)

%http://oeis.org/A000041

\end{document} 